\documentclass[preprint,11pt]{elsarticle}
%\usepackage{numcompress}
%
\usepackage{algcompatible}
\usepackage{algorithm}
%\usepackage{algorithmic}
%\usepackage{caption}

\usepackage{graphics}
\usepackage{graphicx}
\usepackage{epsfig}
 
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{fullpage}
%\biboptions{comma,round}
 
%\journal{Theoretical Computer Science}

\newtheorem{theorem}{Theorem}[section]
%\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
%\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}\newtheorem{example}[theorem]{Example}
\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
\theoremstyle{observation}\newtheorem{observation}[theorem]{Observation}


\newcommand{\comment}[1]{}
%\newcommand{\QED}{\mbox{}\hfill \rule{3pt}{8pt}\vspace{10pt}\par}
%\newcommand{\eqref}[1]{(\ref{#1})}
\newcommand{\theoremref}[1]{(\ref{#1})}
%\newenvironment{proof1}{\noindent \mbox{}{\bf Proof:}}{\QED}
%\newenvironment{observation}{\mbox{}\\[-10pt]{\sc Observation.} }%
%{\mbox{}\\[5pt]}


\def\m{{\rm min}}
%\def\m{\bar{m}}
\def\eps{{\epsilon}}
\def\half{{1\over 2}}
\def\third{{1\over 3}}
\def\quarter{{1\over 4}}
\def\polylog{\operatorname{polylog}}
\newcommand{\ignore}[1]{}
\newcommand{\eat}[1]{}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}

\newcommand{\algorithmsize}[0]{}

%---------------------
%  SPACE SAVERS
%---------------------

%\usepackage{times}
%\usepackage[small,compact]{titlesec}
%\usepackage[small,it]{caption}

\newcommand{\squishlist}{
 \begin{list}{$\bullet$}
  { \setlength{\itemsep}{0pt}
     \setlength{\parsep}{3pt}
     \setlength{\topsep}{3pt}
     \setlength{\partopsep}{0pt}
     \setlength{\leftmargin}{1.5em}
     \setlength{\labelwidth}{1em}
     \setlength{\labelsep}{0.5em} } }
\newcommand{\squishend}{
  \end{list}  }

%---------------------------------
% FOR MOVING PROOFS TO APPENDIX
%\usepackage{answers}
%%\usepackage[nosolutionfiles]{answers}
%\Newassociation{movedProof}{MovedProof}{movedProofs}
%\renewenvironment{MovedProof}[1]{\begin{proof}}{\end{proof}}

\def\e{{\rm E}}
\def\var{{\rm Var}}
\def\ent{{\rm Ent}}
\def\eps{{\epsilon}}
\def\lam{{\lambda}}
\def\bone{{\bf 1}}




\begin{document}

\begin{frontmatter}

\title{Distributed Computation in Dynamic Networks via Random Walks\tnoteref{t1}}
\tnotetext[t1]{A preliminary version of the paper appeared in the proceedings of  26th International Symposium on Distributed Computing (DISC), volume 7611 of LNCS, Springer, pages 136-150, 2012 \cite{disc12}.}


\author[atish]{Atish {Das Sarma}}
\ead{atish.dassarma@gmail.com}

\author[anisur]{Anisur Rahaman Molla}
\ead{anisurpm@gmail.com}

\author[gopal]{Gopal Pandurangan\corref{cor}}
\ead{gopalpandurangan@gmail.com}

%
\cortext[cor]{Supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, Singapore MOE  AcRF Tier 1 grant MOE2012-T1-001-094, and a grant from the US-Israel Binational Science Foundation (BSF). Research done while at Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371.}

%


\address[atish]{eBay Research Labs, eBay Inc., CA, USA.}
\address[anisur]{Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371.}
\address[gopal]{Department of Computer Science, University of Houston, Houston TX, 77204.}




%First definitions. Use these when you want to read comments.
%\def\prasad#1{\marginpar{$\leftarrow$\fbox{P}}\footnote{$\Rightarrow$~{\sf #1 --Prasad}}}
\def\anisur#1{\marginpar{$\leftarrow$\fbox{D}}\footnote{$\Rightarrow$~{\sf #1 --Anisur}}}
%\def\gopal#1{\marginpar{$\leftarrow$\fbox{G}}\footnote{$\Rightarrow$~{\sf #1 --Gopal}}}
%\def\atish#1{\marginpar{$\leftarrow$\fbox{A}}\footnote{$\Rightarrow$~{\sf #1 --Atish}}}
%
%Second definitions. Use these to remove all comments.
\def\anisur#1{}
%\def\danupon#1{}
\def\gopal#1{}
\def\atish#1{}

\begin{abstract}
The paper investigates efficient distributed computation in {\em dynamic} networks in which the
network topology changes (arbitrarily) from round to round.   
Random walks are a fundamental primitive  in a wide variety of network applications; the local
 and lightweight nature of random walks is especially useful for  providing uniform and
efficient solutions to distributed control of dynamic networks.  
Given their  applicability in dynamic networks, we  focus on developing fast distributed algorithms for performing random walks
 in such networks.  %We then present fast algorithms for fundamental  distributed computing problems in dynamic networks using  random walks. 

%In prior work [Das Sarma et al., PODC 2010], a fast distributed
%algorithm for performing random walks was presented for {\em static} networks.  This algorithm's time complexity is 
%sublinear  in the length of the walk ---
%the algorithm performs a random walk of length $\ell$  in
%$\tilde{O}(\sqrt{\ell D})$  rounds\footnote{$\tilde{O}$ hides
%$\polylog{n}$ factors where $n$ is the number of nodes in the
%network.} (with high probability) on an undirected  network, where
%$D$ is the diameter of the network. However, this algorithm and its underlying framework does not apply to a dynamic network. 
Our first contribution is a rigorous framework for the design and analysis of distributed random walk algorithms in dynamic networks. We then develop a fast distributed random walk
based algorithm that runs in $\tilde{O}(\sqrt{\tau \Phi})$ rounds\footnote{$\tilde{O}$ hides
$\polylog{n}$ factors where $n$ is the number of nodes in the
network.} (with high probability), where $\tau$ is the {\em dynamic mixing time}
and $\Phi$ is the {\em dynamic diameter} of the network respectively, and  returns a sample close to a suitably defined stationary distribution of the dynamic network.  %We also apply our fast random walk algorithm to devise fast distributed algorithm for a key problem, namely,  information dissemination in a dynamic network.

Our next contribution is  a fast distributed algorithm 
for the fundamental problem of  information dissemination 
(also called as {\em gossip}) in a dynamic network. In gossip, or more generally,
$k$-gossip, there are $k$ pieces of information (or tokens) that are
initially present in some nodes and the problem is to disseminate the
$k$ tokens to all nodes. 
%In an $n$-node network, solving $n$-gossip  allows nodes to  distributively compute any computable function of their initial inputs using messages of size $O(\log n + d)$, where $d$ is the size of the input to the single node. 
We present a random-walk based algorithm that runs in  $\tilde{O}(\min\{n^{1/3}k^{2/3}(\tau \Phi)^{1/3}, k\Phi \})$ rounds (with high probability).  This is the first $o(k\Phi)$-time fully-distributed {\em token forwarding} algorithm (on certain graph families) that improves over the previous-best $O(k\Phi)$ round distributed algorithm [Kuhn et al., STOC 2010], although in an oblivious adversary model.

The  random walk framework developed in this paper has also subsequently  proved useful in developing efficient storage and search algorithms  as well as
developing fast byzantine agreement algorithms in dynamic networks.

\end{abstract}

\begin{keyword}
Dynamic network, Distributed algorithm, Random walks, Random sampling,   Information dissemination, Gossip.

\end{keyword}

\end{frontmatter}


\input{introduction}

\input{model}

%\input{mixing_time}

\input{results}

\input{related-work}

\input{mixing_time}  

\input{single_rw_algorithm1} 

\input{many_rw_algorithm}

\input{applications1}

\input{conclusion} 


\bibliographystyle{plain}
\bibliography{Distributed-RW}



%\newpage
\section*{Appendix}
%\begin{center}
%\large \textbf{Appendix}
%\end{center}
\appendix
%\section{Moved Proofs}
%\Readsolutionfile{movedProofs}
\input{appendix1}

\end{document}
